package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printInorder

/*
https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
https://leetcode.cn/problems/trim-a-binary-search-tree/description/

669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
 */
class leetcode_669 {
    @Test
    fun test_1() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val root = n1
        n1.left = n0
        n1.right = n2

        val result = trimBST(root, 1, 2)
        val actual = printInorder(result)
        val expect = arrayListOf(1, 2)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root = n3
        n3.left = n0
        n3.right = n4
        n0.right = n2
        n2.left = n1

        val result = trimBST(root, 1, 3)
        val actual = printInorder(result)
        val expect = arrayListOf(1, 2, 3)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
        /**
        题型：二叉搜索树的遍历顺序
         * 若 root.val 小于边界值 low，则 root 的左子树必然均小于边界值，我们递归处理 root.right 即可；
         * 若 root.val 大于边界值 high，则 root 的右子树必然均大于边界值，我们递归处理 root.left 即可；
         * 若 root.val 符合要求，则 root 可被保留，递归处理其左右节点并重新赋值即可。
         */
        // 递归

        // 结束条件
        if (root == null) {
            println("root == null")
            return null
        }

        if (root.`val` < low) { //要删除的节点1
            // 往左遍历
            println("to delete ${root.`val`}, check the right node")
            val right: TreeNode? = trimBST(root.right, low, high) // 判断1的右孩子是否在区间内
            println("to delete ${root.`val`}, return the right node =${right?.`val`} ")
            return right
        } else if (root.`val` > high) { // 要删除的节点4
            // 往右遍历
            println("to delete ${root.`val`}, check the left node ")
            val left: TreeNode? = trimBST(root.left, low, high) // 判断节点4的左孩子是否在区间内
            println("to delete ${root.`val`}, return the left node =${left?.`val`} ")
            return left
        } else {
            println("recursive root ${root.`val`} left =  ${root.left?.`val`}")
            root.left = trimBST(root.left, low, high) // 相当作用于节点3，把节点0的右孩子2接住
            println("set root ${root.`val`} left =  ${root.left?.`val`}")

            println("recursive root ${root.`val`} right =  ${root.right?.`val`}")
            root.right = trimBST(root.right, low, high) // 相当于作用于节点3，把4的左孩子NULL接住
            println("set root ${root.`val`} right =  ${root.right?.`val`}")

            println("return root ${root.`val`}\n")
            return root
        }
    }
}